/*------------------------------------------------------------------------------
$module:      IntArray
$package:     CseApi
$purpose:     TIntArray class definition
$author:      WAYNE WORK STDIO
$CreateAt:    08/07/04
$LastModify:
$license:     Mozilla Public License Version 1.1
------------------------------------------------------------------------------*/

#include "CseApi_.h"

#ifdef _UNICODE
  #define INT_TO_STR(x,buff)       _itow(x,buff,10)
#else
  #define INT_TO_STR(x,buff)       _itoa(x,buff,10)
#endif

TCriticalSection CseIntBuffLock;

struct
{
    TUint32 iSize;
    TUint32 iLen;
    TInt tValue[1];
} __RsvdIntArray = {0,0,{0}};

STATIC TInt *_EmptyTier = __RsvdIntArray.tValue;
const TIntArray& CseEmptyTier = (TIntArray&)_EmptyTier;

#ifdef _DEBUG
TInt32 TotalIntArrayCount = 0;
#endif

class TIntBuffLocker
{
public:
    TIntBuffLocker(void)  { CseIntBuffLock.enter(); }
    ~TIntBuffLocker(void) { CseIntBuffLock.leave(); }
};

STATIC TInt *NewCseIntBlock(int n)
{
    if (n <= 0)
        return _EmptyTier;
    else
    {
        int iLen = sizeof(TUint32[2]) + n * sizeof(TInt);
        TUint32 *pLen = (TUint32 *) new char[iLen];
        pLen[0] = n;
        pLen[1] = n;
        
        return (TInt *) &pLen[2];
    }
}

STATIC TInt *NewCseIntBlock(const TInt *pSour, int iLen, int iExt=0)
{
    int iNewLen = iLen + iExt;
    if (iNewLen <= 0 || (pSour == NULL && iLen > 0))
        return _EmptyTier;
    else
    {
        int iNew = sizeof(TUint32[2]) + iNewLen * sizeof(TInt);
        TUint32 *pLen = (TUint32 *) new char[iNew];
        TInt *ret = (TInt *) &pLen[2];
        pLen[0] = iNewLen;
        pLen[1] = iLen;

        // copy string context
        TInt *pInt = ret;
        for (int i = 0; i < iLen; i++,pInt++,pSour++) *pInt = *pSour;

        return ret;
    }
}

STATIC void TryFreeIntBlock(TInt *pInt)
{
    if (pInt != _EmptyTier)
    {
        char *SourAddr = (char *)pInt - sizeof(TUint32[2]);
        delete []SourAddr;
    }
}

TIntArray::TIntArray()
{
    m_data = _EmptyTier;
#ifdef _DEBUG
    TotalIntArrayCount++;
#endif
}

TIntArray::TIntArray(int MagicNum, TIntArray& tArray)
{
    CHECK_MSG(MagicNum == 20051206,_T("unauthorized call"));
    m_data = tArray.transfer(_EmptyTier);
#ifdef _DEBUG
    TotalIntArrayCount++;
#endif
}

TIntArray::TIntArray(const TIntArray& tArray)
{
    TIntBuffLocker lock;
    m_data = NewCseIntBlock(tArray.m_data,tArray.len());
#ifdef _DEBUG
    TotalIntArrayCount++;
#endif
}

TIntArray::TIntArray(int count)
{
    m_data = NewCseIntBlock(count);
#ifdef _DEBUG
    TotalIntArrayCount++;
#endif
}

TIntArray::TIntArray(const TInt* pSour, int n, int iExt)
{
    TIntBuffLocker lock;

    m_data = NewCseIntBlock(pSour,n,iExt);
#ifdef _DEBUG
    TotalIntArrayCount++;
#endif
}

TIntArray::~TIntArray()
{
    TryFreeIntBlock(m_data);
#ifdef _DEBUG
    TotalIntArrayCount--;
#endif
}

TIntArray& TIntArray::joinEx(const TInt *pSour, int iSourLen)
{
    if (iSourLen <= 0) return *this;  // no need join

    TUint32 *pLen = (TUint32 *) ((char *)m_data - sizeof(TUint32[2]));
    int iTargLen = pLen[1];
    int iTotal   = iTargLen + iSourLen;

    if ((int)pLen[0] >= iTotal)
    {   // have enough space
        TInt *pTarg = m_data + iTargLen;
        for (int i = 0; i < iSourLen; i++,pTarg++,pSour++)
            *pTarg = *pSour;

        pLen[1] = iTotal;
    }
    else
    {   // add more space to hurry up continuous adding
        int iPad = (iTotal + 1) / 2;

        // create enough space and join
        TIntArray ret(m_data,iTargLen,iSourLen + iPad);
        ret.join(pSour,iSourLen);

        // exchange the result and self
        ret.m_data = transfer(ret.m_data);
    }
    return *this;
}

TIntArray& TIntArray::join(const TIntArray& tArray, int index)
{
    TIntBuffLocker lock;
    
    int iSourLen = tArray.len();
    if (index < 0)
    {
        index = iSourLen + index;
        if (index < 0) index = 0;
    }

    return joinEx(tArray.m_data+index,iSourLen-index);
}

TIntArray& TIntArray::join(const TInt *pSour, int iSourLen)
{
    TIntBuffLocker lock;
    return joinEx(pSour,iSourLen);
}

TIntArray& TIntArray::operator=(const TIntArray& tArray)
{
    TIntBuffLocker lock;
    
    int iSourLen = tArray.len();
    TUint32 *pLen = (TUint32 *) ((char *)m_data - sizeof(TUint32[2]));

    if ((int)pLen[0] >= iSourLen)
    {   // has enough space
        TInt *pTarg = m_data;
        TInt *pSour = tArray.m_data;
        for (int i = 0; i < iSourLen; i++,pTarg++,pSour++)
            *pTarg = *pSour;

        pLen[1] = iSourLen;
    }
    else
    {
        TryFreeIntBlock(m_data);
        m_data = NewCseIntBlock(tArray.m_data,iSourLen);
    }
    return *this;
}

void TIntArray::operator+=(const TIntArray& tArray)
{
    TIntBuffLocker lock;
    joinEx(tArray.m_data,tArray.len());
}

void TIntArray::operator+=(TInt i)
{
    join(&i,1);
}

TIntArray TIntArray::multi(int n) const
{
    int iSourLen = len();
    int iTargLen = n * iSourLen;
    if (iTargLen <= 0) return CseEmptyTier;

    TIntArray ret;
    ret.m_data = NewCseIntBlock(iTargLen);
    *(TUint32 *)((char *)ret.m_data - sizeof(TUint32)) = 0;

    TIntBuffLocker lock;
    for (int i = 0; i < n; i++)
        ret.joinEx(m_data,iSourLen);
    return TIntArray(CUT_FROM,ret);
}

TInt& TIntArray::sub(int index) const
{
    TIntBuffLocker lock;
    
    int iLen = len();
    if (index < 0)
        index = index + iLen;

    CHECK_MSG(index >= 0 && index < iLen,_T("access TIntArray out of range"));
    return m_data[index];
}

TInt& TIntArray::operator[](int index) const
{
    return sub(index);
}

TInt *TIntArray::addr() const
{
    return m_data;
}

int TIntArray::len() const
{
    return CSE_ARRAY_LEN(m_data);
}

TBool TIntArray::isEmpty() const
{
    return len() <= 0;
}

TInt TIntArray::compare(const TIntArray& tOther) const
{
    TIntBuffLocker lock;

    if (m_data == tOther.m_data)
        return 0;
    else
    {
        int iSelfLen = len();
        int iOtherLen = tOther.len();

        for (int i = 0; i < iSelfLen; i++)
        {
            if (i >= iOtherLen) return 1; // self array large than other
            
            TInt iRet = m_data[i] - tOther.m_data[i];
            if (iRet != 0) return iRet;
        }
        
        if (iSelfLen == iOtherLen)
            return 0;
        else return -1;  // self array less than other
    }
}

TIntArray TIntArray::slice(int index, int iLen) const
{
    TIntBuffLocker lock;

    int nLen = len();
    if (index < 0)
    {
        index = index + nLen;
        if (index < 0) index = 0;
    }
    
    if (index >= nLen || iLen == 0)
        return TIntArray();
    else
    {
        int iLeft = nLen - index;
        if (iLen == -1 || iLen > iLeft) iLen = iLeft;
        return TIntArray(m_data + index,iLen);
    }
}

TInt *TIntArray::transfer(TInt *pOther)
{
    TInt *ret = m_data;
    if (NULL == pOther)
        m_data = _EmptyTier;
    else
    {
        TUint32 *pLen = (TUint32 *)((char *)pOther - sizeof(TUint32[2]));
        ASSERT_TRUE(pLen[0] >= pLen[1]);
        
        m_data = pOther;
    }
    return ret;
}

TBool TIntArray::copyFrom(const TInt* pSour, int iLen, int iOff) const
{
    if (iOff + iLen > len()) return false;

    TInt *pTarg = m_data + iOff;
    if (pTarg > pSour)
    {   // avoid backward overwrite
        pTarg += iLen - 1;
        pSour += iLen - 1;
        for (int i = iLen-1; i >= 0; i--,pTarg--,pSour--)
            *pTarg = *pSour;
    }
    else if (pTarg != pSour)
    {   // avoid forward overwrite
        for (int i = 0; i < iLen; i++,pTarg++,pSour++)
            *pTarg = *pSour;
    }
    // else, pTarg == pSour, // no need copy
    return true;
}

void TIntArray::insertEx(int iPos, const TInt *pSour, const int iLen)
{
    TUint32 *pLen = (TUint32 *)((char *)m_data - sizeof(TUint32[2]));
    int iTargLen = pLen[1];

    if (iPos == iTargLen)
    {
        joinEx(pSour,iLen);
        return;
    }

    int iTotal = iTargLen + iLen;

    if ((int)pLen[0] >= iTargLen + iLen)  // space is enough
    {
        pLen[1] = iTotal;
        copyFrom(m_data + iPos,iTargLen - iPos,iPos + iLen);
        copyFrom(pSour,iLen,iPos);
    }
    else
    {
        TIntArray ret(iTotal);
        if (iPos > 0)
            ret.copyFrom(m_data,iPos,0);
        ret.copyFrom(pSour,iLen,iPos);
        ret.copyFrom(m_data + iPos,iTargLen - iPos,iPos + iLen);

        // exchange result with this
        ret.m_data = transfer(ret.m_data);
    }
}

TInt TIntArray::append(TInt i)
{
    join(&i,1);
    return i;
}

TIntArray& TIntArray::add(TInt i, int *pIndex)
{
    TIntBuffLocker lock;
    if (pIndex != NULL) *pIndex = len();
    return joinEx(&i,1);
}

void TIntArray::insert(int index, const TInt *pSour, int iLen)
{
    TIntBuffLocker lock;
    if (iLen <= 0) return;
    
    int nLen = len();
    if (index < 0)
    {
        index = index + nLen;
        if (index < 0) index = 0;
    }
    if (index > nLen) index = nLen;

    insertEx(index,pSour,iLen);
}

void TIntArray::remove(int index, int iLen)
{
    TIntBuffLocker lock;

    int nLen = len();
    if (index < 0)
    {
        index = index + nLen;
        if (index < 0) index = 0;
    }
    if (index >= nLen || iLen <= 0) return;

    int iLeft = nLen - index;     // max iLeft items can be deleted
    if (iLen > iLeft) iLen = iLeft;
    int iNewLen = nLen - iLen;

    if (iNewLen <= 0)
    {   // free old buffer
        TryFreeIntBlock(m_data);
        m_data = _EmptyTier;
    }
    else
    {
        copyFrom(m_data + index + iLen,nLen - index - iLen,index);
        truncate(iNewLen);
    }
}

void TIntArray::clear()
{
    TIntBuffLocker lock;
    TryFreeIntBlock(m_data);
    m_data = _EmptyTier;
}

int TIntArray::truncate(int iLen) const
{
    TIntBuffLocker lock;
    if (iLen < 0) iLen = 0;

    int nLen = len();
    if (iLen < nLen)
    {
        TUint32 *pNewLen = (TUint32 *)((char *)m_data - sizeof(TUint32));
        *pNewLen = iLen;
        return iLen;
    }
    else return nLen;
}

STATIC int FindSortIndex(TInt *m_data, int iHigh, TInt iValue)
{
    int iLow = 0;
    int index = -1;
    while (iLow <= iHigh)
    {
        int iHalf = (iLow + iHigh) / 2;
        TInt i = m_data[iHalf] - iValue;

        if (i < 0)
            iLow = iHalf + 1;
        else if (i == 0)
        {
            index = iHalf;
            break;
        }
        else iHigh = iHalf - 1;
    }
    if (index == -1) index = iLow;

    return index;
}

int TIntArray::sortAdd(TInt iValue)
{
    TIntBuffLocker lock;
    
    int index = FindSortIndex(m_data,len()-1,iValue);
    insertEx(index,&iValue,1);
    return index;
}

void TIntArray::sort() const
{
    TIntBuffLocker lock;

    int iCount;
    int iLen = len();
    if (iLen <= 1) return; // no need to sort

    // first make empty-copy and sort-add every item
    TIntArray tTmp(NULL,0,iLen);
    TInt *pSour = addr();
    TInt *pTarg = tTmp.addr();
    for (iCount = 0; iCount < iLen; iCount++,pSour++)
        tTmp.insertEx(FindSortIndex(pTarg,iCount-1,*pSour),pSour,1);

    // then copy back context
    pSour = pTarg; pTarg = addr();
    for (iCount = 0; iCount < iLen; iCount++,pSour++,pTarg++)
        *pTarg = *pSour;
}

int TIntArray::find(TInt iValue, int from) const
{
    TIntBuffLocker lock;

    int iLen = len();
    if (from >= iLen) return -1;

    if (from < 0) from = iLen + from;
    if (from < 0) from = 0;

    TInt *pInt = m_data + from;
    for (int i = from; i < iLen; i++,pInt++)
    {
        if (*pInt == iValue)
            return i;
    }
    return -1;
}

void TIntArray::resize(int iSize)
{
    TIntBuffLocker lock;
    
    TUint32 *pLen = (TUint32 *)((char *)m_data - sizeof(TUint32[2]));
    int iCurrSize = pLen[0];

    if (iCurrSize >= iSize)  // space is enough
        pLen[1] = iSize;
    else
    {   // create enlarged new tier
        TIntArray ret(m_data,pLen[1],iSize - iCurrSize);
        ret.m_data = transfer(ret.m_data); // exchange

        TUint32 *pNewLen = (TUint32 *)((char *)m_data - sizeof(TUint32));
        *pNewLen = iSize;
    }
}

TCharArray TIntArray::str() const
{
    TIntBuffLocker lock;

    TCharArray ret(_T("("));
    int iLen = len();

    TInt *pTarg = m_data;
    for (int i = 0; i < iLen; i++,pTarg++)
    {
        TXchar buff[256];
        if (i == 0)
            ret += INT_TO_STR(*pTarg,buff);
        else
        {
            ret += _T(',');
            ret += INT_TO_STR(*pTarg,buff);
        }
    }
    if (iLen == 1)
        ret += _T(",)");
    else ret += _T(')');

    return ret;
}

TBool TIntArray::enumItem(void*& pIter, TInt *pRet) const
{
    TIntBuffLocker lock;

    if (pIter == NULL)  // start enumlate
        pIter = m_data;
    else pIter = (TInt *)pIter + 1;

    // maybe the dict has resize
    if ((TInt *)pIter < m_data) return false;
    TInt *pEnd = m_data + CSE_ARRAY_LEN(m_data);
    if ((TInt *)pIter < pEnd)
    {
        if (pRet != NULL) *pRet = *(TInt *)pIter;
        return true;
    }
    else return false;
}

TBool operator==(const TIntArray& x, const TIntArray& y)
{
    return x.compare(y) == 0;
}

TBool operator!=(const TIntArray& x, const TIntArray& y)
{
    return x.compare(y) != 0;
}

TBool operator>(const TIntArray& x, const TIntArray& y)
{
    return x.compare(y) > 0;
}

TBool operator>=(const TIntArray& x, const TIntArray& y)
{
    return x.compare(y) >= 0;
}

TBool operator<(const TIntArray& x, const TIntArray& y)
{
    return x.compare(y) < 0;
}

TBool operator<=(const TIntArray& x, const TIntArray& y)
{
    return x.compare(y) <= 0;
}
